public class MyLinkNode {

    static class Node {
        int data;
        Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    public Node head;

    public void creatLink() {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        this.head = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

    }

    public int size() {
        Node cur = head;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    public void display() {
        if (head == null) {
            return;
        }
        Node cur = this.head;
        while (cur != null) {
            System.out.print(cur.data + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    /*public void display(Node node){  //打印某一个节点
        if(head==null){
            return;
        }
        System.out.println(node.data+" ");
        System.out.println();
    }*/
    public void display(Node node) {  //打印某一个节点
        if (node == null) {
            return;
        }
        while (node != null) {
            System.out.println(node.data + " ");
            node = node.next;
        }
    }


    //头插法
    public void addFirst(int data) {
        Node node = new Node(data);
        node.next = this.head;
        head = node;
    }

    public void addLast(int data) {
        Node node = new Node(data);
        Node cur = head;
        if (head == null) {
            head = node;
            return;
        }
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }

    public boolean findLink(int key) {

        Node cur = head;
        while (cur != null) {
            if (cur.data == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    public void addIndex(int pos, int data) {
        Node node1 = new Node(data);
        if (pos == size()) {
            addLast(data);
            return;
        }
        if (pos == 0) {
            addFirst(data);
            return;
        }
        Node node = head;
        if (posLegal(pos)) {
            for (int i = 0; i < pos - 1; i++) {
                node = node.next;
            }
            node1.next = node.next;
            node.next = node1;
        }
    }

    private boolean posLegal(int pos) {
        if (pos < 0 || pos > size()) {
            return false;
        }
        return true;
    }

    public void delLink(int key) {
        Node node = head;
        if (head == null) {
            return;
        }
        if (head.next == null) {
            head = head.next;
            return;
        }
        while (node.next != null) {
            if (node.next.data == key) {
                node.next = node.next.next;
                return;
            }
            node = node.next;
        }

    }

    public void delAll(int key) {
        while (head.data == key && head != null) {
            head = head.next;
        }
        Node pre = head;
        Node cur = head.next;

        while (cur != null) {
            if (cur.data == key) {
                pre.next = cur.next;
                cur = cur.next;
            } else {
                pre = cur;
                cur = cur.next;
            }
        }
    }

    public Node reverseLink() {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        Node cur = head.next;
        head.next = null;
        while (cur != null) {
            Node curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }

    public Node findCenter() {  //寻找中间节点，用快慢指针，偶数个节点和奇数个节点要判断一下结束标志
        if (head == null) {
            return null;

        }
        if (head.next == null) {
            return head;
        }
        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {       // 不能写成fast.next!=null&&fast!=null，因为若fast==null则
            slow = slow.next;                      //fast.next就是空指针异常了，因为null不能了next
            fast = fast.next.next;
        }
        return slow;
    }

    public Node qiuDaoShu(int k) {  //求倒数第k个节点的值，用快慢指针，先让fast走k-1步，然后fast和slow同步走，
        if (k < 0 || head == null) {        //条件是fast.next!=null
            return null;
        }
        Node fast = head;
        Node slow = head;
        while (k - 1 != 0) {
            fast = fast.next;
            if (fast == null) {
                return null;
            }
            k--;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    public Node heBingLink(Node head1, Node head2) {

        Node newnode = new Node(0);
        Node tmp = newnode;
        while (head1 != null && head2 != null) {
            if (head1.data < head2.data) {
                tmp.next = head1;
                tmp = head1;
                head1 = head1.next;
            } else {
                tmp.next = head2;
                tmp = head2;
                head2 = head2.next;
            }
        }
        if (head1 != null) {
            tmp.next = head1;
        }
        if (head2 != null) {
            tmp.next = head2;
        }
        return newnode;
    }

    public Node Partition(int x) {

        Node bs = null;
        Node be = null;
        Node as = null;
        Node ae = null;
        Node cur = this.head;
        while (cur != null) {
            if (cur.data < x) {
                if (bs == null) {
                    bs = cur;
                    be = cur;
                    cur = cur.next;
                } else {
                    be.next = cur;
                    be = be.next;
                    cur = cur.next;
                }
            } else {
                if (as == null) {
                    as = cur;
                    ae = cur;
                    cur = cur.next;
                } else {
                    ae.next = cur;
                    ae = ae.next;
                    cur = cur.next;
                }
            }
        }
        //判断bs为null，as不空，以及bs不空，as为空的情况
        if (bs == null) {
            return as;
        }
        if (as == null) {
            be.next = null;
            return bs;
        }
        ae.next = null;
        be.next = as;
        return bs;

    }

    public Node xiangJiao(Node headA, Node headB) {

        if (headA == null || headB == null) {
            return null;
        }
        Node pl = headA;
        Node ps = headB;
        int lengthA = 0;
        int lengthB = 0;
        int length = 0;
        while (pl != null) {
            lengthA++;
            pl = pl.next;
        }
        while (ps != null) {
            lengthB++;
            ps = ps.next;
        }
        length = lengthA - lengthB;
        if (length > 0) {
            pl = headA;
            ps = headB;
        }
        if (length < 0) {
            pl = headB;
            ps = headA;
            length = lengthB - lengthA;
        }
        while (length > 0) {
            pl = pl.next;
            length--;
        }
        while (pl != ps) {
            pl = pl.next;

            ps = ps.next;
        }
        return pl;

    }


    public boolean hasCycle() {
        Node fast = head;
        Node slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }


    public Node delChongFu(){
        if(head==null){
            return null;
        }
        if(head.next==null){
            return head;
        }
        boolean flag=false;
        Node prev=head;
        Node prepre=head;
        Node cur=head.next;
        while(cur!=null){
            if(prev==head&&flag==false){
                while(cur!=null) {
                    if (prev.data == cur.data) {
                        cur = cur.next;
                        head=cur;
                        if(head==null){
                            return null;
                        }
                    }
                    else{
                        prev=head;
                        break;
                    }
                }

            }
            if(prev.data==cur.data){
               head.next=cur.next;
                cur=cur.next;
            }else{
               prev.next=cur;
               prev=cur;
                cur=cur.next;
            }
            flag=true;
        }

        return head;
    }

    //利用递归逆序打印链表

    public void display3(Node head) {
        Node phead = head;
        if (head == null) {
            return;
        }
        if (phead.next == null) {
            System.out.println(phead.data);
            return;
        }
        display3(phead.next);
        System.out.println(phead);
        return;
    }
    public Node sortInList () {
        Node cur=head;
        int length=0;
         int tmp=0;
        if(head==null){
            return null;
        }
        while(cur!=null){
            cur=cur.next;
            length++;
        }
        for(int i=0;i<length-1;i++){
            cur=head;
            for(int j=0;j<length-1-i;j++){
                if(cur.data>cur.next.data){
                    tmp=cur.data;
                    cur.data=cur.next.data;
                    cur.next.data=tmp;
                }
                cur=cur.next;
            }
        }
        return head;
    }

   // 在指定区间进行链表的翻转
    public Node reverseBetween (Node head, int m, int n) {
        // write code here
        if(head==null){
            return null;
        }
        if(head.next==null){
            return head;
        }
        if(m==1){
            Node prev=head;
            Node head1=head;
            Node cur=prev.next;
            int num=n-m;
            while(num>0){
                Node curNext=cur.next;
                cur.next=head1;
                head1=cur;
                cur=curNext;
                num--;
            }
            prev.next=cur;
            head=head1;
            return head;
        }

        Node prev=head;
        int count=0;
        while(count<m-2){
            prev=prev.next;
            count++;
        }
        Node head1=head;
        head1=prev.next;
        Node head2=prev.next;
        Node cur=head1.next;
        int num=n-m;
        while(num>0){
            Node curNext=cur.next;
            cur.next=head1;
            head1=cur;
            cur=curNext;
            num--;
        }
        prev.next=head1;
        head2.next=cur;
        return head;
    }


}
